//01背包
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算01背包问题的结果
     * @param V int整型 背包的体积
     * @param n int整型 物品的个数
     * @param vw int整型二维数组 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
     * @return int整型
     */
    public int knapsack (int V, int n, int[][] vw) {
        // write code here
        int len = vw.length;
        int[][] dp = new int[len+1][V+1];

        for (int i = 1; i < V+1; i++) {
            for (int j = 1; j < len+1; j++) {
                dp[j][i] = 
vw[j-1][0] <= i ? Math.max(dp[j-1][i], vw[j-1][1]+dp[j-1][i - vw[j-1][0]]) : dp[j-1][i];
            }
        }
        return dp[len][V];
    }
}
给定一个长度为 n 的无序数组 A ，包含正数、负数和 0 ，请从中找出 3 个数，使得乘积最大，返回这个乘积。

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 最大乘积
     * @param A int整型一维数组 
     * @return long长整型
     */
    public long solve (int[] A) {
        // write code here
        //将前三个数进行排序
        Arrays.parallelSort(A);
        long a = A[A.length-1];
        long b = A[A.length-2];
        long c = A[A.length-3];
        long d = A[0];
        long e = A[1];
        return a*b*c > a*d*e ? a*b*c : a*d*e;
    }
}
//120
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int len = triangle.size();
        int[][] dp = new int[len][len];
        dp[0][0] = triangle.get(0).get(0);
        for (int i = 0; i < len; i++) {
            for (int j = 1; j < len; j++) {
                dp[i][j] = Integer.MAX_VALUE/2;
            }
        }
        for (int i = 1; i < len; i++) {
            dp[i][0] = dp[i-1][0]+triangle.get(i).get(0);
        }
        for (int i = 1; i < len; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i][j] = Math.min(dp[i-1][j], dp[i-1][j-1]) + triangle.get(i).get(j);
            }
        }
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < len; i++) {
            min = Math.min(min, dp[len-1][i]);
        }
        return min;
    }
}

